package fun.coding.leetcode;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Set;
import java.util.Stack;

public class BinaryTreePostorderTraversal {

	public static void main(String[] args) {
		BinaryTreePostorderTraversal btpt = new BinaryTreePostorderTraversal();
		
		/*      1
		 *    2   3
		 *  4   5
		 *  post order-> 4 5 2 3 1  
		 */
		TreeNode root = new TreeNode(1);
		root.left = new TreeNode(2);
		root.right = new TreeNode(3);
		root.left.left = new TreeNode(4);
		root.left.right = new TreeNode(5);
		
		// List<Integer> res = btpt.postorderTraversal(root);
		List<Integer> res = btpt.postorderUsingSet(root);
		for (int i : res) {
			System.out.println(i);
		}
	}
	
	/**
	 * http://en.wikipedia.org/wiki/Tree_traversal#Iterative_Traversal
	 */
	public List<Integer> postorderTraversal(TreeNode root) {
		Stack<TreeNode> stack = new Stack<TreeNode>();
		
		List<Integer> res = new LinkedList<Integer>();
		
		if (root == null) return res;
		TreeNode cur = root;
		TreeNode lastVisitedNode = null;
		
		while (!stack.isEmpty() || cur != null) {
			if (cur != null) {
				stack.push(cur);
				cur = cur.left;
			} else {
				TreeNode t = stack.peek();
				
				// Avoid a dead loop to revisit the right child of the node
				if (t.right != null && t.right != lastVisitedNode) {
					cur = t.right;
				} else {
					res.add(t.val);
					lastVisitedNode = stack.pop();
				}
			}
		}
		return res;
	}
	
	// A iterative solution with a processed set
	public List<Integer> postorderUsingSet(TreeNode root) {
		List<Integer> res = new LinkedList<Integer>();
		
		if (root == null) return res;
		
		Stack<TreeNode> s = new Stack<TreeNode>();
		Set<TreeNode> processed = new HashSet<TreeNode>();
		
		s.push(root);
		
		while (!s.isEmpty()) {
			TreeNode cur = s.pop();
			
			if (processed.contains(cur)) {
				res.add(cur.val);
				continue;
			}
			
			s.push(cur);
			if (cur.right != null) s.push(cur.right);
			if (cur.left != null) s.push(cur.left);
			
			processed.add(cur);
		}
		return res;
	}
	
	
	
	public List<Integer> postorderTraversalRecursion(TreeNode root) {
		List<Integer> res = new LinkedList<Integer>();
		
		if (root == null) return res;
		
		helper(root, res);
		return res;
	}
	
	private void helper(TreeNode root, List<Integer> res) {
		if (root == null) return;
		
		helper(root.left, res);
		helper(root.right, res);
		res.add(root.val);
	}
}
